AGC 016 题解
016 的难度比 015 高 ~
智商被完虐了。。【失去梦想.jpg】
A
枚举最终变成哪个字母
B
容易发现 min 与 max 相差不超过 1
若 min = max，则要么每种颜色都是 1 个，要么每种颜色都有 2 个以上
若 min + 1 = max，分类讨论就好了，样例大良心 qvq
C
透过样例 2 我们看出，若 n 是 h 的倍数且 m 是 w 的倍数，不可能构造
那么我们应该使得 n % h、m % w 的部分的贡献尽量大。这边提供一种乱搞思路：定一个较大的值为 d，对于 (h 倍数，w 倍数) 的位置放 -(hw - 1)d - 1，其余位置放 d
D
不错的思维题
容易发现，若将异或值视为 n + 1 位的序列元素，整个操作就等价于不断将 x (1 <= x <= n) 位置与 n + 1 位置的元素交换
题解方法非常神仙：
若 ai != bi，则从 ai 向 bi 连边
最终答案 = 总边数 + 连通块数 - 1
注意这里的总边数是不考虑 n + 1 的
大小为 x 连通块需要 x - 1 次，块与块之间 n + 1 位置的转换需要 1
对于第 n + 1 个位置单独考虑，若它独一个点则是要考虑到连通块里的
正确性可以分类讨论一下，比较显然。
E
伪概率题，超级无敌妙！解法容易理解，却想不到哇。。
考虑钦定一只活到最后的鸡，设它为 i。
它能活着，必然有其他的鸡为它而死，那么我们维护一个集合，表示为 i 死的鸡有哪些。
考虑时间倒流。每当集合里的鸡出现时，我们将另一只鸡加入集合；若另一只鸡已经在集合中，那么这只钦定的鸡活不到最后。
枚举两只活到最后的鸡，判他们的集合是否交，若交则无解，因为一只鸡不能死两次。
真就 留着你是为了炖了你呗（
具体实现用 bitset，O(nm + n^3 / 32)，注意 bitset & 操作是 O(n) 的
F
sg(1) ^ sg(2) != 0 不好考虑，正难则反，我们用 2^m - ( sg(1) = sg(2) 的方案数 )
考虑边集显然不现实，我们考虑点集。
将 DAG 中的点按照 sg 值分层，显然点 1 和点 2 在同一层
根据分层，想到子集dp，f[S] 表示只考虑 S 这个点集使得 sg(1) = sg(2) 的方案数（注意 S 必须同时包含或不包含 1 和 2）
转移就枚举 S 的子集 T，设 U 为补集，其中 T 中 sg 值都不为 0，U 中 sg 值都为 0（U 其实就是底层点集），也就是说 1 和 2 必须同时在 T 中或者 U 中
统计方案的四条规则：
- U 不能内部连边
- T 内部就是 f[T]
- T 中每个点都至少有一条到 U 的边（T 中 sg 值 += 1）
- U 到 T 随便连